package leetcode.editor.cn;

import java.util.*;
import leetcode.editor.common.*;

public class FindAllAnagramsInAString {

  public static void main(String[] args) {
    Solution solution = new FindAllAnagramsInAString().new Solution();
    // put your test code here
    System.out.println(solution.findAnagrams("bbae", "abb"));
  }
  // leetcode submit region end(Prohibit modification and deletion)

  // leetcode submit region begin(Prohibit modification and deletion)
  class Solution {
    public List<Integer> findAnagrams(String s, String p) {
      // 字串出现的次数
      Map<String, Integer> needMap = new HashMap<>();
      for (int i = 0; i < p.length(); i++) {
        needMap.put(p.substring(i, i + 1), needMap.getOrDefault(p.substring(i, i + 1), 0) + 1);
      }

      // 窗口Map
      Map<String, Integer> windowMap = new HashMap<>();
      int left = 0;
      int right = 0;
      // 当 valid == needMap.size()，代表窗口已经符合条件
      int valid = 0;

      // 记录结果
      final List<Integer> res = new ArrayList<>();

      while (right < s.length()) {
        final String rightChar = s.substring(right, right + 1);
        right++;

        // 包含字串
        if (needMap.containsKey(rightChar)) {
          windowMap.put(rightChar, windowMap.getOrDefault(rightChar, 0) + 1);
          // 出现的次数一致 ，代表有效
          if (windowMap.get(rightChar).equals(needMap.get(rightChar))) {
            valid++;
          }
        }

        // 判断左侧是否需要收缩
        // 如果窗口长度 已经 比 字串小，肯定不用收缩
        while (right - left >= p.length()) {
          // 窗口已经符合条件
          if (valid == needMap.size()) {
            res.add(left);
          }

          final String leftStr = s.substring(left, left + 1);
          left++;
          // final char leftChar = s.charAt(left);
          // 窗口数据更新
          if (needMap.containsKey(leftStr)) {

            if (windowMap.get(leftStr).equals(needMap.get(leftStr))) {
              valid--;
            }
            windowMap.put(leftStr, windowMap.get(leftStr) - 1);
          }
        }
      }
      return res;
    }
  }
}
